package kyssion.leetcode.num1_50;

import kyssion.leetcode.util.ListNode;

/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 */
public class code23_N个链表合并 {
    public static void main(String[] args) {
        int[] i = new int[]{
                1, 2, 3
        };
        int num = 4;
        ListNode[] listNodes = new ListNode[num];
        for (int a = 0; a < num; a++) {
            listNodes[a] = ListNode.createListNode(ListNode.createArray(a));
        }
        listNodes = new ListNode[1];
        listNodes[0] = null;
//        listNodes[1]=null;
        ListNode listNode = new code23_N个链表合并().mergeKLists2(listNodes);
        ListNode.showListNode(listNode);
    }

    /**
     * 一般思路,for循环遍历获取数据
     * 事件复杂度 n*length1+(n-1)*length2+...+1*lengthn
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(-1);
        ListNode item = head;
        while (true) {
            int minItemVal = Integer.MAX_VALUE;
            ListNode minItem = null;
            int index = -1;
            for (int a = 0; a < lists.length; a++) {
                if (lists[a] != null && lists[a].val < minItemVal) {
                    minItem = lists[a];
                    minItemVal = lists[a].val;
                    index = a;
                }
            }
            if (minItem == null) {
                break;
            }
            lists[index] = minItem.next;

            minItem.next = item.next;
            item.next = minItem;
            item = minItem;
        }
        return head.next;
    }

    /**
     * 使用小顶堆来事实现优化
     * 事件复杂读 lengthALL*log2(n)
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        ListNode head = new ListNode(-1);
        ListNode nowNode = head;
        int nowlength = lists.length;
        lists = buildMixState(lists, nowlength);
        while (lists[0] != null && nowlength > 0) {
            nowNode.next = lists[0];
            nowNode = nowNode.next;
            if (lists[0].next != null) {
                lists[0] = lists[0].next;
            } else {
                lists[0] = lists[nowlength - 1];
                nowlength--;
            }
            rebuild(lists, 0, nowlength);
        }
        return head.next;
    }

    private ListNode[] buildMixState(ListNode[] lists, int length) {
        for (int a = length - 1; a >= 0; a--) {
            rebuild(lists, a, length);
        }
        return lists;
    }

    private void rebuild(ListNode[] lists, int i, int length) {
        ListNode before = lists[i];
        while (true) {
            int left = (i + 1) * 2 - 1;
            int right = (i + 1) * 2;
            int minIndex = getMinIndex(lists, left, right, length);
            if (minIndex != -1 && (before == null || (lists[minIndex] != null && lists[minIndex].val < before.val))) {
                lists[i] = lists[minIndex];
                i = minIndex;
            } else {
                lists[i] = before;
                return;
            }
        }
    }

    private int getMinIndex(ListNode[] lists, int left, int right, int length) {
        if (left >= length) {
            return right >= length ? -1 : lists[right] == null ? -1 : right;
        } else {
            if(right>=length){
                if(lists[left]==null){
                    return -1;
                }
                return left;
            }else{
                if(lists[right]==null){
                    if(lists[left]==null){
                        return -1;
                    }
                    return left;
                }else{
                    if(lists[left]==null) {
                        return right;
                    }else{
                        return lists[left].val>lists[right].val?right:left;
                    }
                }
            }
        }
    }


    /**
     * 分治方法实现优化 时间复杂度
     * lengthALL*Log2(n)
     * 理解一下为什么这个比第一种方法快
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists3(ListNode[] lists) {
        return partion(lists, 0, lists.length - 1);
    }

    public ListNode partion(ListNode[] lists, int s, int e) {
        if (s == e) {
            return lists[s];
        }
        if (s < e) {
            int q = (s + e) / 2;
            ListNode l1 = partion(lists, s, q);
            ListNode l2 = partion(lists, q + 1, e);
            return merge(l1, l2);
        } else {
            return null;
        }
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        return mergeKLists(new ListNode[]{l1, l2});
    }


    /**
     * 分治升级版 , 分治策略本事上是将大事件拆分成小事件并且消除叠加损耗的方法
     * 这里使用循环代替了递归
     * @param lists
     * @return
     */
    public ListNode mergeKLists4(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        int m = n;
        int t = 0;
        while(m>1){
            // System.out.println(m);
            int i = 0;
            if ((m&1) != 0){
                t++;
                i = 1;
            }
            for (;i<m-1;i+=2){
                //    System.out.println(t);
                ListNode a = merge2(lists[i],lists[i+1]);
                lists[t] = a;
                t++;

            }
            m = t;
            t = 0;
        }
        return lists[0];
    }
    public static ListNode merge2(ListNode a,ListNode b){
        if ((a==null)&&(b==null)){
            return a;
        }
        ListNode c = new ListNode(0);
        ListNode h = c;
        while((a!=null)&&(b!=null)){
            if (a.val<b.val){
                c.next = a;
                c = c.next;
                a = a.next;
            }else{
                c.next = b;
                c = c.next;
                b = b.next;
            }


        }
        if (a != null){
            c.next = a;
        }
        if (b != null){
            c.next = b;
        }
        return h.next;
    }
}
